package datastructure;

public class LongestIncreasingSeq {

	public int longestSeq(int[] a) {
		int n = a.length;
		int[] stack = new int[n];
		int[] prev = new int[n];
		int top = -1;
		stack[++top] = 0;
		prev[top] = -1;
		for (int i = 1; i < n; ++i) {
			int l = 0, r = top, m;
			while (l <= r) {
				m = l + r >> 1;
				if (a[stack[m]] >= a[i]) {// modify to > for nondecreasing
					r = m - 1;
				} else {
					l = m + 1;
				}
			}
			stack[r + 1] = i;
			prev[i] = (r == -1 ? r : stack[r]);
			if (r == top)
				top++;
		}
		return top + 1;
	}

	public static void main(String[] args) {
		LongestIncreasingSeq lis = new LongestIncreasingSeq();
		int[] a = new int[] { 1, 3, 3, 3, 6, 2, 4, 5, 6 };
		System.out.println(lis.longestSeq(a));
	}

}
